package com.lw.leetcode.arr.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * 1091. 二进制矩阵中的最短路径
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/12 9:51
 */
public class ShortestPathBinaryMatrix {

    public static void main(String[] args) {
        ShortestPathBinaryMatrix test = new ShortestPathBinaryMatrix();


        int a = 100;
        int b = 99;
        int c = (a << 8) + b;

        System.out.println(c >> 8);
        System.out.println(c & 255);
        System.out.println((a << 8) + b);


        // 2
//        int[][] arr = {{0,1}, {1,0}};

        // 14
        int[][] arr = {
                {0, 1, 1, 0, 0, 0},
                {0, 1, 0, 1, 1, 0},
                {0, 1, 1, 0, 1, 0},
                {0, 0, 0, 1, 1, 0},
                {1, 1, 1, 1, 1, 0},
                {1, 1, 1, 1, 1, 0}
        };

        int i = test.shortestPathBinaryMatrix(arr);
        System.out.println(i);
    }

    public int shortestPathBinaryMatrix(int[][] grid) {

        LinkedList<Integer> queue = new LinkedList<>();

        int n = grid.length;


        if (grid[0][0] == 0) {
            queue.add(0);
            grid[0][0] = 2;
        }


        while (!queue.isEmpty()) {
            int value = queue.pop();
            int x = value >> 8;
            int y = value & 255;
            int c = grid[x][y];
            boolean a1 = x > 0;
            boolean a2 = x < n - 1;
            boolean b1 = y > 0;
            boolean b2 = y < n - 1;
            if (a1 && b1) {
                int a = x - 1;
                int b = y - 1;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (a1) {
                int a = x - 1;
                int b = y;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (a1 && b2) {
                int a = x - 1;
                int b = y + 1;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (b2) {
                int a = x;
                int b = y + 1;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (a2 && b2) {
                int a = x + 1;
                int b = y + 1;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (a2) {
                int a = x + 1;
                int b = y;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (a2 && b1) {
                int a = x + 1;
                int b = y - 1;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
            if (b1) {
                int a = x;
                int b = y - 1;
                if (grid[a][b] == 0) {
                    queue.add((a << 8) + b);
                    grid[a][b] = c + 1;
                }
            }
        }
        return grid[n - 1][n - 1] > 1 ? grid[n - 1][n - 1] - 1 : -1;
    }
}
